#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
class ListNode;
//使用 using 定义别名，NodePtr 表示指向 ListNode 的指针类型
using NodePtr = ListNode*;
// 链表节点结构
class ListNode {
public:
	int val;  // 节点存储的值，命名为val，表示value
	NodePtr next;  // 指向下一个节点的指针，使用别名 NodePtr
	ListNode(int value = 0, NodePtr n = nullptr) : val(value), next(n) {}
	
	// 在 ListNode 类中实现打印方法
	void printList() const {
		const ListNode* current = this;
		while (current) {
			std::cout << current->val << " ";
			current = current->next;
		}
		std::cout << std::endl;
	}
};

class LinkedList;
using List = LinkedList;

class LinkedList{
public:
	LinkedList() : head(nullptr){ }
	// 功能：在链表头部插入节点
	void insertAtHead(int val);
	
	// 功能：在链表尾部插入节点
	void insertAtTail(int val);
	
	// 功能：删除指定值的节点
	void deleteNode(int val);
	
	//打印链表
	void printList();
	
	//打印search结果
	void printResult(int val);
	
	//以迭代实现链表反转
	NodePtr iterateReverseList();
	
	//隐藏递归实现反转链表的细节
	void reverse(){
		recursionReverseList(head);
	}
	
	//获取链表长度
	int getLength();
	
	//合并两个有序链表
	NodePtr mergeSortedLists(NodePtr, NodePtr);
	
	//获取head
	NodePtr getHead() const{return head;}
	
	/*
	快慢指针算法（Floyd 判圈算法，也称为龟兔赛跑算法）是一种用于检测链表中是否存在环的经典算法。
	该算法使用两个指针，一个慢指针（slow）和一个快指针（fast）。慢指针每次移动一步，而快指针每次移动两步。
	如果链表中存在环，那么快指针最终会追上慢指针；如果链表中不存在环，快指针会先到达链表的末尾。
	*/
	bool hasCycle();
	
	/*
	快慢指针算法是一种在链表操作中非常实用的技巧，它通过使用两个指针，一个慢指针（slow）和一个快指针（fast），
	以不同的速度遍历链表。慢指针每次移动一步，而快指针每次移动两步。当快指针到达链表末尾时，慢指针正好处于链表的中间位置
	*/
	
	NodePtr findMiddleNode();
private:
	// 功能：查找链表中是否存在指定值的节点，存在返回true，否则返回false
	bool search(int val);
	
	//以递归实现反转链表
	void recursionReverseList(NodePtr);
	
	
private:
	NodePtr head; //头节点
};
#endif

